1. Field of the Invention
The present invention relates to a SQRT (Square Root) calculator, and more particularly to a SQRT calculator capable of reducing an amount of calculation and having a simple hardware structure.
The present application is based on Korean Patent Application No. 2002-7753, which is incorporated herein by reference.
2. Background of the Related Art
FIG. 1 is a schematic diagram showing a hardware construction of a conventional seed-type SQRT calculator. The SQRT calculator 10 comprises a selection signal output unit 11, a slope storage unit 13, a y-intercept storage unit 15, a multiplier 17 and an adder 19.
The selection signal output unit 11 transmits a slope selection signal and a y-intercept selection signal to the slope storage unit 13 and the y-intercept storage unit 15 to select a slope and a y-intercept, respectively, necessary for calculation of a square root with respect to an input datum. The selection signal output unit 11 also transmits the input datum to the multiplier 17.
The slope storage unit 13 stores the slope necessary for calculation of the square root. On receiving the slope selection signal from the selection signal output unit 11, the slope storage unit 13 transmits the slope corresponding to the received selection signal to the multiplier 17.
The y-intercept storage unit 15 stores the y-intercept necessary for calculation of the square root. On receiving the y-intercept selection signal from the selection signal output unit 11, the y-intercept storage unit 15 transmits the y-intercept corresponding to the received selection signal to the adder 19.
The multiplier 17 multiplies the slope from the slope storage unit 13 by the received datum from the selection signal output unit 11, to transmit the resulting value to the adder 19. The adder 19, then, adds the received values from the y-intercept unit 15 and multiplier 17. The following equation represents above described arithmetic relations.output datum=slope×input datum+y-intercept  [Equation 1]
Generally, the SQRT calculator in FIG. 1 uses an approximation method by representing preliminary calculation results as a graph, as shown in FIG. 2, and diving the graph into linearized sub-regions. As shown in FIG. 2, respective square roots are calculated to be represented as a graph and these values are divided into 7 sub-regions to be linearized.
This method forms 7 fractional lines represented by 7 linear equations, respectively. Thus, 7 slopes and y-intercepts, respectively, are needed to calculate a square root of an input number. The sub-regions can be set as needed. If those sub-regions are more than 7, then each of a slope and a y-intercept with respect to each sub-region is needed.
FIG. 3 is a flow chart illustrating the step of calculating a square root by the SQRT calculator in FIG. 1. As shown in FIG. 3, the selection signal output unit 11 generates an address corresponding to each of the sub-regions set as described above (S301). The slope storage unit 13 and y-intercept storage unit 15 store a slope and a y-intercept, respectively, corresponding to each of the sub-regions. The selection signal output unit 11 transmits a selection signal to the slope storage unit 13 and y-intercept storage unit 15 to select the slope and y-intercept corresponding to the generated address. The selection signal output unit 11 also transmits an input datum to the multiplier 17. The slope storage unit 13 outputs the slope corresponding to the selection signal from the selection signal output unit 11 to the multiplier 17. The y-intercept storage unit 15 transmits the y-intercept corresponding to the received selection signal from the selection signal output unit 11 to the adder 19 (S303). The multiplier 17 multiplies the received input datum by the y-intercept to output the resulting value to the adder 19. The adder 19 adds the value from the multiplier 17 and the y-intercept from the y-intercept storage unit 15 (S305). The adder 19 outputs the resulting value which is calculated as above Equation 1 (S307). This terminates the calculation of the square root by the SQRT calculator.
Besides the above described method, a Newton-Raphson algorithm is used to calculate a square root. The Newton-Raphson algorithm is based on a following Equation 2.
                                                                        Y                                  k                  +                  1                                            =                            ⁢                                                                    Y                    k                                    -                                                                                    Y                        k                        2                                            -                      X                                                              2                      ⁢                                              Y                        k                                                                                            =                                                      1                    2                                    ⁢                                      (                                                                  Y                        k                                            +                                              X                                                  Y                          k                                                                                      )                                                                                                                                          Y                                  k                  +                  1                                            =                            ⁢                                                Y                  k                                -                                                      f                    ⁡                                          (                                              Y                        k                                            )                                                                            f                    ⁡                                          (                                              Y                        k                                            )                                                                                                                                                              f                ⁡                                  (                  Y                  )                                            =                            ⁢                                                Y                  2                                -                X                                                                        [                  Equation          ⁢                                          ⁢          2                ]            
In the Newton-Raphson algorithm, the more iteration performed, the more accurate the calculation result. For a calculation of a square root of 0.7, for example, 3 times iteration is needed for an accurate result, as shown in Table 1. Here, X is 0.7 and Y is 0.5.
TABLE 1K01234Yk050.950.84340.83670.8367
Comparing the above-described two methods, it can be noticed that the method using the seed-type SQRT calculator is more convenient to obtain a result than the method using the Newton-Raphson algorithm.
However, the conventional SQRT calculator is subject to an error due to its seed-type structure as shown in FIG. 4. With 7 seeds and an input datum, a number between 1 and 105, it can be noticed in FIG. 5 that an error, which is a difference between a true square root and a square root calculated by the seed-type SQRT calculator, of maximum 6 is caused. It can also be noticed that errors for boundary points of each sub-regions are 0, but errors for inner points of each sub-regions, which are far from the boundaries, i.e. an arrowed point as shown in FIG. 4, become much larger.
To minimize these errors, the conventional SQRT calculator needs to reduce the intervals of its sub-regions, thereby causing the number of coefficients to be stored to increase. When parallel processing is adopted to calculate a square root in accordance with each of the divided sub-regions by the conventional SQRT calculator, calculation speed increases, but the volume of the hardware increases since separate units such as multipliers and adders are needed for processing calculation of each of the sub-regions.
The method using the Newton-Raphson algorithm, on the other hand, has a disadvantage in that a number of iterations of calculation are needed to obtain an accuracy and the volume of the hardware increases since additional divider and differentiator besides multiplier are needed on implementation.